//#include <iostream>
//#include <fstream>
//#include <sstream>
//#include <string>
//#include <unordered_map>
//#include <queue>
//#include <set>
//#include <vector>
//#include <ctime>
//#include <algorithm>
//#include <assert.h>
//#include <math.h>
//#include <random>
#include<bits/stdc++.h>

using namespace std;

// 客户节点
struct CNode{
	string name;                    //客户节点的ID，ID字符串的长度不超过 2
	vector<int> demandSeqs;         //客户节点的需求序列（即每时刻的带宽需求），其值不超过 550,000MB
	vector<int> validEs;            //客户节点包含的有效时延范围内的边缘节点序号
	CNode(){}//空参构造器
	CNode(string name){//带参构造器
		this->name = name;
	}
};
// 边缘节点
struct ENode{
	string name;                      //边缘节点的ID，ID字符串的长度不超过 2
	int bandWidth;                    //边缘节点的带宽上限，其值不超过 1,000,000MB
	int leftBW;                       //边缘节点当前剩余可分配带宽
	int beforeBW;                     //记录该节点分配前的剩余可分配带宽
	vector<int> validCs;              //边缘节点包含的有效时延范围内的客户节点序号
	ENode(){}//空参构造器
	ENode(string name, int bandWidth){//带参构造器
		this->name = name;
		this->bandWidth = bandWidth;
		this->leftBW = bandWidth;
		this->beforeBW = bandWidth;
	}
};                                   
								      
// 定义全局变量                       
int T, M, N;                           //T表示时刻数(1<T≤8928)，M表示客户节点数(1≤𝑀≤35)，N表示边缘节点数(1≤𝑁≤135)
int LIMIT_QoS;                         //QoS约束上限
vector<string> timeSeqs;               //时间序列，长度为 T
vector<CNode> cNodes;                  //客户节点，长度为 M
vector<ENode> eNodes;                  //边缘节点，长度为 N
unordered_map<string, int> cIdxs;      //记录客户节点对应的序号
unordered_map<string, int> eIdxs;      //记录边缘节点对应的序号
vector<vector<int>> qos;               //边缘节点到客户节点的时延(0<QoS≤1000ms)，大小为 N*M
vector<vector<vector<int>>> timeAns; //ans表示每时刻，每个客户节点，获取每个边缘节点的流量。在某时刻，每一行满足客户流量需求，每一列满足边缘节点带宽上限约束

// 定义文件所在路径
# define DEMAND_CSV "/data/demand.csv"
# define SITE_BANDWIDTH_CSV "/data/site_bandwidth.csv"
# define QOS_CSV "/data/qos.csv"
# define CONFIG_INI "/data/config.ini"
//# define DEMAND_CSV "./pressure_data/demand.csv"
//# define SITE_BANDWIDTH_CSV "./pressure_data/site_bandwidth.csv"
//# define QOS_CSV "./pressure_data/qos.csv"
//# define CONFIG_INI "./pressure_data/config.ini"
# define OUTPUT_FILE "/output/solution.txt"

/********* 读数据 ***************/
string Trim(string& str){
	str.erase(0,str.find_first_not_of(" \t\r\n"));
	str.erase(str.find_last_not_of(" \t\r\n") + 1);
	return str;
}
// 读取配置文件
void readConfig(){
	ifstream fp(CONFIG_INI, ios::in);
	string line,tempstr;
	getline(fp, line);//跳过第一行
	getline(fp, line);
	size_t pos = line.find('=');
	string key = line.substr(0, pos);
	LIMIT_QoS = stoi(line.substr(pos+1));
	fp.close();
}
// 读取所有客户节点在不同时刻的带宽需求
void readDemandCsv(){
	ifstream fin(DEMAND_CSV);
	string line, field;
	// 处理第一行
	getline(fin, line);
	istringstream sin(line);//string数据流化
	getline(sin, field, ',');//跳过第一行第一个元素
	int client_number = 0;
	while(getline(sin, field, ',')){
		field = Trim(field);
		cNodes.push_back(CNode{field});
		cIdxs[field] = client_number++;
	}
	M = client_number;//客户节点数量
	//处理剩余行
	while(getline(fin, line)){
		istringstream iss(line);//string数据流化
		getline(iss, field, ',');//每行第一个元素形成时间序列
		timeSeqs.push_back(Trim(field));
		client_number = 0;
		while(getline(iss, field, ',')){
			field = Trim(field);
			CNode &node= cNodes[client_number++];
			node.demandSeqs.push_back(stoi(field));
		}
	}
	T = timeSeqs.size();//时刻数量
}
// 读取所有边缘节点的带宽上限
void readSiteBandWidthCsv(){
	ifstream fin(SITE_BANDWIDTH_CSV);
	string line, name, size;
	getline(fin, line);//跳过第一行
	//处理剩余行
	int edge_number = 0;
	while(getline(fin, line)){
		istringstream sin(line);//string数据流化
		getline(sin, name, ',');//每行第一个元素
		getline(sin, size, ',');//每行第二个元素
		size = Trim(size);
		eNodes.push_back(ENode{name, stoi(size)});
		eIdxs[name] = edge_number++;
	}
	N = eNodes.size(); //边缘节点数量
}
// 读取边缘节与客户节点之间的网络时延
void readQosCsv(){
	//初始化N*M大小的qos矩阵
	for(int n=0; n<N; n++){
		vector<int> temp(M);
		qos.push_back(temp);
	}
	ifstream fin(QOS_CSV);
	string line, clientName, edgeName, q;
	vector<string> clienNames;//记录该文件第一行中的客户节点名
	getline(fin, line);
	istringstream sin(line);
	getline(sin, q, ',');//忽略首行第一个元素
	while(getline(sin, clientName, ',')) clienNames.push_back(Trim(clientName));
	//处理其余行
	int eIdx, cIdx;
	while(getline(fin, line)){
		istringstream iss(line);//string数据流化
		getline(iss, edgeName, ',');//每行第一个元素
		int c = 0;
		eIdx = eIdxs[edgeName];
		while(getline(iss, q, ',')){
			q = Trim(q);
			cIdx = cIdxs[clienNames[c++]];
			qos[eIdx][cIdx] = stoi(q);
		}
	}
}
// 读文件
void readData(){
	readConfig();
	readDemandCsv();
	readSiteBandWidthCsv();
	readQosCsv();
	// 计算每个客户节点的 validEs
	for(int c=0; c<M; c++){
		CNode &node = cNodes[c];
		for(int e=0; e<N; e++){
			if(qos[e][c] < LIMIT_QoS){
				node.validEs.push_back(e);
			}
		}
	}
	// 计算每个边缘节点的 validCs
	for(int e=0; e<N; e++){
		ENode &node = eNodes[e];
		for(int c=0; c<M; c++){
			if(qos[e][c] < LIMIT_QoS){
				node.validCs.push_back(c);
			}
		}
	}
}
/**********************************/

// 写结果
void writeResults(){
	ofstream outfile;
	outfile.open(OUTPUT_FILE);
	if(!outfile){
		cout << "error for opening ouput file" << endl;
	}else{
		for(int t=0; t<T; t++){
			for(int c=0; c<M; c++){
				//输出每个客户节点的分配方案
				outfile<<cNodes[c].name<<":";
				int num = 0;
				for(int e=0; e<N; e++){
					if(timeAns[t][c][e]>0){
						num++;
						if(num==1) outfile<<"<"<<eNodes[e].name<<","<<timeAns[t][c][e]<<">";
						else outfile<<",<"<<eNodes[e].name<<","<<timeAns[t][c][e]<<">";
					}
				}
				outfile<<endl;
			}
		}
		outfile.close();
	}
}
// 计算成本
int computeCost(){
	int totalCost = 0;
	int p95 = ceil(T * 0.95)-1;
	vector<vector<int>> edgeSeqs(N, vector<int>(T,0));//每个边缘节点的带宽序列
	for(int t=0; t<T; t++){
		for(int c=0; c<M; c++){
			for(int e=0; e<N; e++){
				if(timeAns[t][c][e] > 0){
					edgeSeqs[e][t] += timeAns[t][c][e];
				}
			}
		}
	}
	for(int e=0; e<N; e++){
		sort(edgeSeqs[e].begin(), edgeSeqs[e].end());
		totalCost += edgeSeqs[e][p95];
	}
	return totalCost;
}

// 处理带宽需求
void handleDemands(){
	int p95 = ceil(T * 0.95)-1;                           //95分位的时刻
	vector<vector<int>> rest(T, vector<int>(N, 0));       //记录某时刻某边缘节点剩余带宽
	vector<vector<int>> dds(T, vector<int>(M, 0));        //记录某时刻某客户节点剩余需求
	for(int t=0; t<T; t++){
		for(int e=0; e<N; e++) rest[t][e] = eNodes[e].bandWidth;
		for(int c=0; c<M; c++) dds[t][c] = cNodes[c].demandSeqs[t];
	}
	
	//试着考虑每个边缘节点
	vector<int> ens(N);
	for(int i=0; i<N; i++) ens[i]=i;
	sort(ens.begin(), ens.end(), [](int &e1, int &e2){
		return eNodes[e1].bandWidth > eNodes[e2].bandWidth;
	});
	for(int &e:ens){
		ENode &eNode = eNodes[e];             //当前边缘节点
		vector<int> validCs = eNode.validCs;  //有效客户
		vector<int> times(T), totalDs(T);
		for(int t=0; t<T; t++){
			times[t] = t;
			for(int c:validCs) totalDs[t] += dds[t][c]/cNodes[c].validEs.size()+0.1*dds[t][c];
		}
		sort(times.begin(), times.end(), [totalDs](int &t1, int &t2){return totalDs[t1] < totalDs[t2];});
		//处理大于p95的时刻
		for(int tt=T-1; tt>p95; tt--){
			int t = times[tt];
			for(int c:validCs){
				if(dds[t][c]==0) continue;
				if(rest[t][e] >= dds[t][c]){
					timeAns[t][c][e] += dds[t][c];
					rest[t][e] -= dds[t][c];
					dds[t][c] = 0;
				}else if(rest[t][e] > 0){
					timeAns[t][c][e] += rest[t][e];
					dds[t][c] -= rest[t][e];
					rest[t][e] = 0;
				}
				if(rest[t][e] == 0) break;
			}
		}
	}
	
	//补漏
	for(int t=0; t<T; t++){		
		for(int c=0; c<M; c++){
			if(dds[t][c]==0) continue;
			vector<int> &validEs = cNodes[c].validEs;
			while(dds[t][c] != 0){
				for(int &e:validEs){
					if(rest[t][e] > 0){
						rest[t][e]--;
						dds[t][c]--;
						timeAns[t][c][e]++;
					}
					if(dds[t][c]==0) break;
				}
			}
		}
	}
}

// 程序主入口
int main() {
	// 读数据
	readData();
	
	// 初始化 T*M*N 的数组，用来存答案
	for(int t=0; t<T; t++){
		vector<vector<int>> ans(M, vector<int>(N,0));
		timeAns.push_back(ans);
	}
	
	// 处理需求
	handleDemands();
	
	// 写结果
	writeResults();
	// 计算成本
	//int totalCost = computeCost();
	//cout<<"Total Cost："<<totalCost<<endl;
	//
    //std::cout << "Hello world!"<<std::endl;
	return 0;
}
